import java.util.Arrays;

/**
 * @author LKQ
 * @date 2022/2/22 14:03
 * @description 采用基数排序将时间复杂度降为O(n)
 */
public class FormalSolution {
    public static void main(String[] args) {
        FormalSolution formalSolution = new FormalSolution();
        formalSolution.maximumGap(new int[]{3, 6, 9, 1});
    }
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        long exp = 1;
        int[] buf = new int[n];
        int maxVal = Arrays.stream(nums).max().getAsInt();
        while (maxVal >= exp) {
            int[] cnt = new int[10];
            for (int i = 0; i < n; i++) {
                int digit = (nums[i] / (int)exp) % 10;
                cnt[digit]++;
            }
            for (int i = 1; i < 10; i++) {
                cnt[i] += cnt[i-1];
            }
            for (int i = n-1; i >= 0 ; i--) {
                int digit = (nums[i] / (int)exp) % 10;
                buf[cnt[digit] - 1] = nums[i];
                cnt[digit]--;
            }
            System.arraycopy(buf, 0, nums, 0, n);
            exp *= 10;
        }
        int ret = 0;
        for (int i = 1; i < n; i++) {
            ret = Math.max(ret, nums[i] - nums[i-1]);
        }
        return ret;
    }
}
